The precise modeling of moving geometric shapes has a high degree of importance in numerous applications, e.g., CAD/CAM (computer-aided design and manufacturing) applications and computer graphics, visualization, and imaging applications. In general, modeling of moving geometric shapes is performed by an operation commonly known as sweep (or sweeping). If a shape is defined by a set of points S, and the set S moves on path M, the sweep of S along M is the set of points swept (or occupied) by S at some time during the motion. To explain sweep mathematically, it is first valuable to review several background concepts of spatial modeling.
Consider a shape (a set of points) S with its own coordinate system F.sub.s moving in a d-dimensional Euclidean space W with respect to some global fixed coordinate system F.sub.w. Following the notation assigned by reference 10 of the Bibliography at the end of this disclosure, the motion of the shape S can be expressed as M(t), t .epsilon. [0,1], a one-parameter set of transformations in the higher-dimensional configuration space C. For the purposes of this invention, the concepts of "transformation" and "motion" are interchangeable and are commonly represented by matrices. Additionally, this discussion will refer to rigid body motions for illustration purposes but, except when noted, all discussion and results apply to general non-singular affine transformations in E.sup.d.
At every instant t=a, the original point x of S moves to a new location that is determined by the transformation M(a). Superscript notation will be used to define the transformed points (and set of points) as EQU x.sup.M(a) =M(a).multidot.x, S.sup.M(a) =M(a)S (1)
The transformation q .epsilon. M(t) for some instantaneous value t determines the position and orientation of F.sub.s with respect to F.sub.w at that instant and therefore determines the coordinates of every point x.sup.q of the moving set S with respect to F.sub.w. By definition, a point x .epsilon. S is located at x.sup.M(0) with respect to F.sub.w.
In the special (but common) case of rigid body motion in three-dimensional Euclidean space, each transformation M(a) specifies rotation and translation of S at time a with respect to F.sub.w. Rigid body motion in a d-dimensional space is determined by d(d+1)/2 independent degrees of freedom as a path in the configuration space C. The mathematical properties of such a configuration space are well understood (see, e.g., reference 10 of the Bibliography at the end of this disclosure).
For a range of values of t, M(t) is a subset of the configuration space C. For brevity, the set M(t), t .epsilon. [0,1] may simply be denoted as M. A motion M specifies how the moving coordinate system F.sub.s moves with respect to the fixed coordinate system F.sub.w. Every point x of set S moves with respect to F.sub.w according to M, as illustrated in FIG. 1. Two-dimensional examples are used for clarity, but the same arguments hold in any d-dimensional space. As t goes from 0 to a, the moving point x.sup.M(t) sweeps, with respect to the fixed frame F.sub.w, a set of points T.sub.x called the trajectory of x. The trajectory T.sub.x is defined as ##EQU1##
Each instantaneous transformation M(a) in equation (1) has a unique inverse M (a) such that x=M (a)[M(a)x]. Given a transformation M(t) for a range of values of t .epsilon. [0,1], we will call transformation M (t) inverted if it is the inverse of M(t) for every instance of t.
Consider the point y as being the copy of point x .epsilon. S in F.sub.w at the initial configuration. Point y is fixed in F.sub.w and does not move with set S, but rather it moves relative to S. To an observer placed at the origin of F.sub.s the moving point x .epsilon. S will appear to be fixed while the fixed coordinate system F.sub.w, and the point y fixed in F.sub.w, will appear to be moving according to the inverted motion M (t). In other words, the moving observer will see the inverted trajectory ##EQU2##
This is illustrated in FIG. 2. Note that the point y is introduced only to illustrate the difference between what the observer sees from the two coordinate systems F.sub.w and F.sub.s. To paraphrase, the trajectory of the moving point x, observed from F.sub.w, is generated by the motion M, while the trajectory of the same point x, observed from F.sub.s, is generated by the inverted motion M. Intuitively, T.sub.x represents the trace left by moving point x as seen from F.sub.w, while T.sub.x is the trace of x as seen from F.sub.s. Therefore, while observed from the fixed coordinate system F.sub.w, the points x of S are moving according to M, and while observed from the moving coordinate system F.sub.s, the "world" appears to be moving according to M. For example, when M is a pure translation, the two trajectories T.sub.x and T.sub.x are simply reflections of one another with respect to the origin, i.e., T.sub.x =-T.sub.x (see, e.g., reference 17).
To introduce the concept of relative motion, consider a moving set E that moves according to the absolute motion M.sub.E, and denote the absolute motion of set S by M.sub.S. In the general case, two objects always move relative to each other. Sometimes one of the objects is at rest with respect to F.sub.w, which is only a particular case wherein the relative motion between the two objects happens to be identical with the absolute motion. One can express the relative motion in any coordinate system that can be defined in the space of the objects, but it is usually expressed in one of the coordinate systems attached to each of the two objects and which moves together with the objects. Since sets S and E move relative to each other, their relative motion can be expressed in a coordinate system attached to S by EQU M.sub.S/E =M.sub.E.sup.-1 M.sub.S (4)
and, consequently, in a coordinate system F.sub.E attached to E by EQU M.sub.E/S =M.sub.S.sup.-1 M.sub.E (5)
Equation (4) expresses points of F.sub.s in F.sub.E, while equation (5) expresses points of F.sub.E in F.sub.s.
It is then relevant to review how relative motions and trajectories can be represented in projective space. General affine transformations in E.sup.d can be represented as linear transformations in projective space using homogeneous coordinates and (d+1) .times.(d+1) matrices (see, e.g., reference 17). Thus, if motion M(t) is given by a matrix A(t), then the inverted motion M (t) is given by the inverse of this matrix A.sup.-1 (t). In the case of a rigid body motion in E.sup.3, this may be depicted as ##EQU3## where .theta.(t) and .tau.(t) respectively represent the rotational and translational components of the motion M(t). In the case of pure rotation, .tau.(t)=0 and A.sup.-1 (t) is obtained from A(t) by replacing the orthonormal sub-matrix .theta.(t) with its transpose .theta..sup.T (t). When M(t) is a pure translation, .theta.(t) is the identity, and A.sup.-1 (t) is obtained from A(t) by replacing .tau.(t) with its reflection -.tau.(t).
If a point x is represented by a vector .nu., and a motion M(t) is represented by a matrix A(t), the trajectory T.sub.x can be written in parametric form simply as A(t) .nu..
The parametric form of the curve T.sub.x is suitable for computing the intersection of T.sub.x with the boundary of a given set (typically solid) S, as needed for the PMC procedure developed below. In the general case, this representation of T.sub.x would use trigonometric functions, and it may be useful to re-parameterize T.sub.x in a computationally more convenient form.
With this background in mind, sweep may be formally expressed as ##EQU4## where S.sup.q denotes set S positioned according to q. Following the above notation and definitions from equations (1) and (2), equation (8) can be reexpressed as ##EQU5## where the sweep M(t)S is the "trace" left by a set of points S that is moving according to M(t), t .epsilon. [0,1]. This is illustrated schematically by FIG. 3, wherein a rectangular 2-dimensional set S in general motion M with respect to a fixed coordinate system is shown.
The formulations of equations (8) and (9) assume that the sweep is computed from the fixed coordinate system F.sub.w, "observing" the moving coordinate system F.sub.s.
Sweep can also be defined as observed from the moving coordinate system F.sub.s : ##EQU6## The sweep of set S according to the inverted motion M is quite distinct from that defined in equation (8), as illustrated by FIG. 4. Note that in both definitions of sweep, the trajectories of distinct points of S generated by the same transformation M(t) need not be congruent, and in general the relationship between these trajectories is not simple.
It must be remembered that sweeping is technically not a method for modeling shapes, but rather a method for modeling the motion of a known shape, or more informally, the "track" or space traversed by a shape in motion. Sweeping is nevertheless extensively used to assist in constructing and modeling shapes and surfaces in both academic and commercial systems, as discussed in the references cited in the later Bibliography. However, as these references also note, sweeping is subject to both intrinsic mathematical or logical limitations, as well as practical computational limitations regarding the size and complexity of the operation.
One major limitation is that sweeps of simple shapes moving in simple motions can be computed in special situations, but not for general shapes and motions. As an example, sweeps of simple shapes (e.g., linear polyhedra) moving in simple linear translations can be computed, but sweeps of complex shapes (shapes more general than linear polyhedra) which rotate and/or translate nonlinearly can run afoul of both the intrinsic and practical problems noted above. In particular, while several methods for generating candidate surfaces bounding the sweep are known (see references 1, 12, and 19 of the Bibliography at the end of this disclosure), robust procedures for a point membership classification (PMC) to determine if a given point is in, on, or out of the sweep defined by expression (8) have been identified only in special situations (see, e.g., reference 7 of the Bibliography). Such situations include: restricting the type of the moving object S, for example to a ball, a convex polyhedron, or a planar cross-section that remains orthogonal to the trajectory; allowing only simple motions M that prevent self-intersections in the sweep, or limiting them to simple translations and rotations; formulating PMC procedures in terms of heuristic numerical sampling and searching algorithms; using rendering methods to compute the image of the sweep without actually computing the complete representation of the sweep; or combinations of some or all of these approaches.
A second major limitation is that in order to perform the sweep operation, both the shape and its motion must be defined. While this limitation may seem so apparent that it does not merit mention, it implies a more subtle disadvantage: the object of most design and modeling efforts is to determine a suitable or optimal shape, and since sweeping cannot be performed with an unknown shape, sweeping does not provide direct assistance in determining a suitable or optimal shape. In this situation, sweeping is used for testing shapes that are initially proposed by designers. To illustrate with a more specific example, consider the problem of part collision (interference) in mechanical design. Interference of static (fixed) parts within an assembly or enclosing envelope can be determined in a straightforward fashion by computing intersection of the corresponding solid models of the parts. Packaging of moving parts by use of the sweep operation is more difficult. A typical situation is shown in FIG. 5: a part S having a defined shape (the shape either being proposed or final) moves within envelope E according to motion M, and must fit inside E while in motion in order to avoid interference. A common way to approach this problem has been to test if E .andgate. sweep(S,M)=.phi. (if the intersection between E and the sweep of S according to M is empty) or if sweep(S,M)--E is not equal to .phi., as illustrated in FIG. 6. This test may be difficult to implement owing to the limitations of sweeps noted above. Even when fully implemented, the result of the test is binary: a "yes" or "no" answer is generated, and a "no" answer only indicates that interference occurs without suggesting how S should be modified to fit inside E during M. To perform such modifications, designers must use their experience and intuition to successively redesign and test new shapes S, and this iterative process is inefficient and costly; see, e.g., publication 8 in the Bibliography below.